package leetcode.code2466;

public class Solution {

	int mod = (int) 1e9 + 7;

	public int countGoodStrings(int low, int high, int zero, int one) {
		long[] dp = new long[high + 1];
		dp[0] = 1;
		long ans = 0;
		for (int i = 0; i < dp.length; i++) {
			if (i >= low && i <= high) {
				ans += dp[i];
				ans %= mod;
			}
			if (i + zero <= high) {
				dp[i + zero] += dp[i];
				dp[i + zero] %= mod;
			}
			if (i + one <= high) {
				dp[i + one] += dp[i];
				dp[i + one] %= mod;
			}
		}
		return (int) ans;
	}
}
